// https://www.lintcode.com/problem/n-queens/description

class Solution {
public:
    /*
     * @param n: The number of queens
     * @return: All distinct solutions
     */
    vector<string> getPuzzle(vector<int> record, int n)
    {
        vector<string> puzzle(n, "");
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                puzzle[i] += (record[i] == j)?'Q':'.';
            }
        }
        return puzzle;
    }
    bool valid(vector<int> record, int col) //任两个皇后都不能处于同一条横行、纵行或斜线上
    {
        int row = record.size();
        for (int i = 0; i < row; ++i)
        {
            if (record[i] == col)
            {
                return false;
            }
            // if (i - record[i] == row - col) // 判断在斜线上
            // {
            //     return false;
            // }
            // if (i + record[i] == row + col)
            // {
            //     return false;
            // }
            if (abs(i - row) == abs(record[i] - col)) return false; 
        }
        return true;
    }
    void search(vector<vector<string>>& result, vector<int>& record, int n)
    {
        if (record.size() == n) 
        {
            result.push_back(getPuzzle(record, n));
            return;
        }
        for (int i = 0; i < n; ++i)
        {
            if (!valid(record, i)) continue;
            record.push_back(i);
            search(result, record, n);
            record.pop_back();
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<int> record;
        search(result, record, n);
        return result;
    }
};